#ifndef _AVL_TREE_H
#define _AVL_TREE_H

struct AvlNode;
typedef struct AvlNode *PtrToNode;
typedef PtrToNode Position;
typedef PtrToNode AvlTree;
typedef int ElementType;

AvlTree MakeEmpty(AvlTree T);
Position Find(ElementType X, AvlTree T);
Position FindMin(AvlTree T);
AvlTree Insert(ElementType X, AvlTree T);
AvlTree Delete(ElementType X, AvlTree T);
ElementType Retrieve(Position P);
void PrintTree(AvlTree T);
struct AvlNode
{
    ElementType Element;
    Position Left;
    Position Right;
    int Height;
    //懒惰删除
    int Deleted;
};
#endif